//
// Created by fengg on 2020/4/25.
//

#include <stdio.h>
#include <stdlib.h>

const static char _WELCOME[] =
        "    二 叉 树 子 系 统（191003600107 冯国宇）    "    "\n"
        " ********************************************"    "\n"
        "*           1---------建 二 叉 树             *"   "\n"
        "*           2---------凹 入 显 示             *"   "\n"
        "*           3---------先 序 遍 历             *"   "\n"
        "*           4---------中 序 遍 历             *"   "\n"
        "*           5---------后 序 遍 历             *"   "\n"
        "*           6---------层 次 遍 历             *"   "\n"
        "*           7---------求 叶 子 数             *"   "\n"
        "*           8---------求 结 点 数             *"   "\n"
        "*           9---------求 树 深 度             *"   "\n"
        "*           0---------返      回              *"   "\n"
        " ********************************************"    "\n";

#define _MAX(a,b) ((a) > (b) ? (a) : (b))

typedef void (*EVENT)();

typedef struct _bin_tree {
    char data;
    struct _bin_tree  *parent;
    struct _bin_tree  *l_child;
    struct _bin_tree  *r_child;
} BinTree ;

typedef struct _queue {
    BinTree **_q;
    size_t size;
    size_t count;
    int head;
    int tail;
} Queue ;

typedef struct _static_entry{
    char data;
    int l_entry;
    int r_entry;
} StaticEntry ;

typedef struct _stack {
    BinTree **_s;
    int top;
    size_t size;
} Stack;

void init_queue(Queue **pQueue,size_t t){
    if(!*pQueue){
        *pQueue = calloc(1, sizeof(Queue));
        (*pQueue)->_q = calloc(t, sizeof(void*));
    }
    (*pQueue)->size  =  t;
    (*pQueue)->count =  0;
    (*pQueue)->head  = -1;
    (*pQueue)->tail  = -1;
}

int is_queue_empty(Queue *pQueue){
    return pQueue->head == pQueue->tail;
}

int is_queue_filled(Queue *pQueue){
    return pQueue->count+1 >= pQueue->size;
}

void init_stack(Stack **s,size_t size){
    if(!*s){
        *s = malloc(sizeof(Stack));
    }
    (*s)->_s = calloc(size, sizeof(void *));
    (*s)->size = size;
    (*s)->top = -1;
}

int is_stack_empty(Stack *pStack){
    return pStack->top < 0;
}

int push(Stack *pStack,BinTree *pBinTree){
    pStack->_s[++pStack->top] = pBinTree;
    return 0;
}
int pop(Stack *pStack,BinTree **pBinTree){
    if(is_stack_empty(pStack))
        return -1;
    *pBinTree  = pStack->_s[pStack->top--];
    return 0;
}

int in_queue(Queue *pQueue,BinTree *pBinTree){
    if(!is_queue_filled(pQueue)){
        ++pQueue->tail;
        pQueue->_q[pQueue->tail%=pQueue->size] = pBinTree;
        ++pQueue->count;
        return 0;
    }
    return 1;
}
int out_queue(Queue *pQueue,BinTree **pBinTree){
    if(is_queue_empty(pQueue))
        return 1;
    ++pQueue->head;
    *pBinTree = pQueue->_q[pQueue->head%=pQueue->size];
    --pQueue->count;
    return 0;
}
static BinTree *GLOBAL_TREE;

/// TODO  Deprecated
enum {
    END_MODE = 0,
    DEPTH_MODE = 9
};



BinTree* CreatBinTree(){
    BinTree *pTree;
    char data;
    scanf("%c%*c",&data);
    if (data == '0')
        return NULL;
    else { //🞏
        pTree = malloc(sizeof(BinTree));
        pTree->data = data;
        printf("请输入%c结点的左子结点:",data);
        pTree->l_child = CreatBinTree();
        printf("请输入%c结点的右子结点:",data);
        pTree->r_child = CreatBinTree();
    }
    return pTree;
}

void _pre_erg(BinTree *root){
    if(!root)
        return;
    printf("%c ",root->data);
    _pre_erg(root->l_child);
    _pre_erg(root->r_child);
}
void _mid_erg(BinTree *root){
    if(!root)
        return;
    _mid_erg(root->l_child);
    printf("%c ",root->data);
    _mid_erg(root->r_child);
}
void _tai_erg(BinTree *root){
    if(!root)
        return;
    _tai_erg(root->l_child);
    _tai_erg(root->r_child);
    printf("%c ",root->data);
}

void _lel_erg(Queue *pQueue){
    int ERR = 0;
    BinTree *pBinTree;
    if(is_queue_empty(pQueue))
        return;

    ERR = out_queue(pQueue,&pBinTree);
    if(ERR){
        printf("\n[ERROR] out_queue IN FUNCTION _lel_erg\n");
        return;
    }
    printf("%c ",pBinTree->data);
    if(pBinTree->l_child)
       ERR = in_queue(pQueue,pBinTree->l_child);
    if(pBinTree->r_child)
       ERR =  in_queue(pQueue,pBinTree->r_child);
    if(ERR){
        printf("\n[ERROR] RUNNING OUT QUEUE IN FUNCTION _lel_erg\n");
        return;
    }
    _lel_erg(pQueue);
}

int _cotyledon(BinTree *pBinTree){
    int total=0;
    if(!pBinTree)
       return 0;
    if(!pBinTree->l_child && !pBinTree->r_child )
       return 1;
    total += _cotyledon(pBinTree->l_child);
    total += _cotyledon(pBinTree->r_child);
    return total;
}

/* 1 */
void input(){
    printf("请输入根结点:");
    GLOBAL_TREE = CreatBinTree();
}
/* 2 */

#define MAX_WIDTH                   60
#define INIT_WIDTH                  10
#define PADDING_WIDTH               5
const static char PADDING_CHAR  =  ' ';
const static char ENDING_CHAR   =  '-';
#define STACK_SIZE 32
void show(){
    Stack *pStack = NULL;
    int depth[STACK_SIZE] = {0x0};
    BinTree *pBinTree;
    int width = INIT_WIDTH,max_width=MAX_WIDTH,i;
    init_stack(&pStack,STACK_SIZE);
    push(pStack,GLOBAL_TREE);
    depth[pStack->top] = width;
    while (!is_stack_empty(pStack)){
        width = depth[pStack->top];
        pop(pStack,&pBinTree);
        for (i = 0; i < width; ++i) putchar(PADDING_CHAR);
        printf("%c ",pBinTree->data);
        for (i = width+1; i < max_width; ++i) putchar(ENDING_CHAR);
        putchar('\n');
        if(pBinTree->r_child){
            push(pStack,pBinTree->r_child);
            depth[pStack->top] = width+PADDING_WIDTH;

        }
        if(pBinTree->l_child){
            push(pStack,pBinTree->l_child);
            depth[pStack->top] = width+PADDING_WIDTH;

        }
    }
}
/* 3 */
void pre_erg(){
    printf("前序遍历GLOBAL THREE\n");
    _pre_erg(GLOBAL_TREE);
    putchar('\n');
}
/* 4 */
void mid_erg(){
    printf("中序遍历GLOBAL THREE\n");
    _mid_erg(GLOBAL_TREE);
    putchar('\n');
}
/* 5 */
void tai_erg(){
    printf("后序遍历GLOBAL THREE\n");
    _tai_erg(GLOBAL_TREE);
    putchar('\n');
}
/* 6 */
void lel_erg(){
    Queue *table = NULL;
    init_queue(&table,16);
    in_queue(table,GLOBAL_TREE);
    printf("层次遍历GLOBAL_TREE\n");
    _lel_erg(table);
    putchar('\n');
}
/* 7 */
void cotyledon(){
    int total=0;
    total =  _cotyledon(GLOBAL_TREE);
    printf("总子叶数: %d\n",total);
}

int _node(BinTree *pBinTree) {
    int total = 1;
    if(!pBinTree)
        return 0;
    total += _node(pBinTree->r_child);
    total += _node(pBinTree->l_child);
    return total;
}

/* 8 */
void node(){
    int total = 0;
    total =  _node(GLOBAL_TREE);
    printf("总结点数: %d\n",total);
}

int _depth(BinTree *pBinTree) {
    int lChildDep,rChildDep;
    if (!pBinTree){
        return 0;
    }
    lChildDep = _depth(pBinTree->l_child);
    rChildDep = _depth(pBinTree->r_child);

    return _MAX(lChildDep,rChildDep)+1;
}

/* 9 */
void depth(){
    int dep=0;
    dep = _depth(GLOBAL_TREE);
    printf("深度 %d\n",dep);
}
void Ahoukuse(){
    int temp_l,temp_r;
    int index=0,max_len=0;
    char temp_c;
    StaticEntry raw_data[20];
    BinTree *binTreeArr[20] = {0x0};
    scanf("%c %d %d%*c",&temp_c,&temp_l,&temp_r);
    while (temp_c != '0' || temp_l || temp_r){
        raw_data[index].data = temp_c;
        raw_data[index].l_entry = temp_l;
        raw_data[index++].r_entry = temp_r;
        scanf("%c %d %d%*c",&temp_c,&temp_l,&temp_r);
    }
    max_len = index;
    while (--index >=0){
        binTreeArr[index] = calloc(1,sizeof(BinTree));
        binTreeArr[index]->data = raw_data[index].data;

    }
    while (++index < max_len){
        binTreeArr[index]->r_child = raw_data[index].r_entry  ?
                                     binTreeArr[raw_data[index].r_entry]:NULL;
        binTreeArr[index]->l_child = raw_data[index].l_entry  ?
                                     binTreeArr[raw_data[index].l_entry]:NULL;
    }
    GLOBAL_TREE = binTreeArr[0];
}
/* 0 */
void end(){
    puts("Bye~");
    exit(0);
}
EVENT dispatch_router[11] = {
    end,
    input,
    show,
    pre_erg,
    mid_erg,
    tai_erg,
    lel_erg,
    cotyledon,
    node,
    depth,
    Ahoukuse
};

void draw() {
    puts(_WELCOME);
}


void Dispatcher(int MODE){
    EVENT Event = dispatch_router[MODE];
    Event();
}

void init() {
    GLOBAL_TREE = calloc(1, sizeof(BinTree));
    draw();
}

int main(){
    int MODE;
    char *temp_str,*offset;
    temp_str = calloc(8, sizeof(char));
    offset = temp_str;
    init();
    while (1){
        puts("请选择菜单号:");
        scanf("%s%*c",temp_str);
        MODE = strtol(temp_str,&offset,10);
        if(MODE < END_MODE || MODE > DEPTH_MODE+1){
            printf("\n[ERROR] %d IS INVALID MODE,TRY AGAIN\n",MODE);
            continue;
        } else if(temp_str == offset){
            printf("\n[ERROR] %s NOT A NUMBER,TRY AGAIN\n",temp_str);
            continue;
        }
        Dispatcher(MODE);
    }
}

